package com.uhu.code;

import com.uhu.code.help.TreeNode;

/**
 * todo
 * Definition for a binary tree no{
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        if(preorder.length == 0) {
            return root;
        }
        int delimiter = 0;
        for(int i = 0; i < inorder.length; i++){
            if(preorder[0] == inorder[i]){
                delimiter = i;
                break;
            }
        }
        root.left = buildTree(getArray(preorder, 1, delimiter + 1), getArray(inorder, 0, delimiter));
        root.right = buildTree(getArray(preorder, delimiter + 1, preorder.length), getArray(inorder, delimiter + 1, inorder.length));
        return root;
    }

    private int [] getArray(int[] arr, int start, int end){
        if(end < start){
            return new int[0];
        }
        int [] result = new int[end - start];
        for(int i = start; i < end; i++){
            result[i - start] = arr[i];
        }
        return result;
    }

    public static void main(String[] args) {
        Solution105 solution105 = new Solution105();
        solution105.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(solution105);
    }
}
